class Solution
{
public:
    vector<bool> findAnswer(int n, vector<vector<int>> &edges)
    {
        vector<vector<pair<int, int>>> graph(n);
        for (auto &edge : edges)
        {
            graph[edge[0]].emplace_back(edge[1], edge[2]);
            graph[edge[1]].emplace_back(edge[0], edge[2]);
        }

        vector<int> dist(n, INT_MAX);
        vector<unordered_set<int>> minPathFrom(n);

        priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
        pq.emplace(0, 0);
        dist[0] = 0;

        while (!pq.empty())
        {
            auto [d, u] = pq.top();
            pq.pop();

            if (d > dist[u])
            {
                continue;
            }

            for (auto &[v, w] : graph[u])
            {
                if (dist[v] > dist[u] + w)
                {
                    dist[v] = dist[u] + w;
                    minPathFrom[v].clear();
                    minPathFrom[v].insert(u);
                    pq.emplace(dist[v], v);
                }
                else if (dist[v] == dist[u] + w)
                {
                    minPathFrom[v].insert(u);
                }
            }
        }

        int m = edges.size();
        vector<bool> result(m, false);
        unordered_map<long long, int> edgeToIndex;
        for (int i = 0; i < m; ++i)
        {
            int u = edges[i][0];
            int v = edges[i][1];

            if (u > v)
            {
                swap(u, v);
            }
            edgeToIndex[1LL * u * m + v] = i;
        }

        queue<int> q;
        q.push(n - 1);
        while (!q.empty())
        {
            int u = q.front();
            q.pop();

            for (int v : minPathFrom[u])
            {
                int uu = u;
                int vv = v;
                if (uu > vv)
                {
                    swap(uu, vv);
                }
                int index = edgeToIndex[1LL * uu * m + vv];
                result[index] = true;
                q.push(v);
            }
        }
        return result;
    }
};